import java.util.*;
/*
 * @lc app=leetcode.cn id=54 lang=java
 *
 * [54] 螺旋矩阵
 */

// @lc code=start
class Solution {
    // 我记得我在算法竞赛入门那本书上写过这道题来着。
    // 参考PTA 1050
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length , n = matrix[0].length;//m>=1，所以不用判断m!=0;
        List<Integer> ans = new ArrayList<>();
        int tot = 0, N = m*n;//统计结束条件的。
        int x= 0 ,y=0;
        boolean[][] visited = new boolean[m][n];//标记访问过的位置的，比每次m--,n--方便

        ans.add(matrix[x][y]);//先把0,0给加进去
        visited[0][0]=true;

        while(tot!= N-1){
            /**
             * 注意这里最好从++y开始，不然后续处理麻烦
             * 如果采用y++,那么y最后是会取到n的，所以在下一步还要y--。
             * 如果用++y,[0,0]位置需要先添加进来
             */
            while(y+1<n && !visited[x][y+1]) {
                ans.add(matrix[x][++y]);
                tot++;
                visited[x][y]=true;
            }
            while(x+1<m && !visited[x+1][y]) {
                ans.add(matrix[++x][y]);
                tot++;
                visited[x][y]=true;
            }
            while(y-1>=0 && !visited[x][y-1]) {
                ans.add(matrix[x][--y]);
                tot++;
                visited[x][y]=true;
            }
            while(x-1>=0 && !visited[x-1][y]) {
                ans.add(matrix[--x][y]);
                tot++;
                visited[x][y]=true;
            }

        }

        return ans;
    }
}
// @lc code=end

